primes up to 10^8 Algorithm
In abstract algebra, objects that behave in a generalized manner like prime numbers include prime components and prime ideals. A prime number (or a prime) is a natural number greater than 1 that is not a merchandise of two smaller natural numbers. method that are restricted to specific number forms include Pépin's test for Fermat numbers (1877), Proth's theorem (c. 1878), the Lucas – Lehmer primality test (originated 1856), and the generalized Lucas primality test.
#include<iostream>
#include <cstring>
char prime[100000000];
void Sieve(int64_t n) {
memset(prime, '1', sizeof(prime)); // intitize '1' to every index
prime[0] = '0'; // 0 is not prime
prime[1] = '0'; // 1 is not prime
for (int p = 2; p * p <= n; p++) {
if (prime[p] == '1') {
for (int i = p * p; i <= n; i += p)
prime[i] = '0'; // set all multiples of p to false
}
}
}
int main() {
Sieve(100000000);
int64_t n;
std::cin >> n; // 10006187
if (prime[n] == '1')
std::cout << "YES\n";
else
std::cout << "NO\n";
}
